import java.util.Arrays;

public class Algorithm {
    public static void main(String[] args) {
        int[] arr = {12,24,9,37,28,135,66,88,99,44,667};
        //Sort.heapSort(arr);
        //Sort.radixSort(arr,0, arr.length - 1,Sort.maxDigit(arr));
        //System.out.println(Arrays.toString(arr));
        System.out.println("I'm going to learning bintree tomorrow!");
    }
}

class Sort {

    public static void swap(int[] arr, int p, int q) {
        int t = arr[p];
        arr[p] = arr[q];
        arr[q] = t;
    }
    public static void heapSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int heapSize = arr.length;
        swap(arr, 0, --heapSize);
        while (heapSize > 0) {
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }
    }
    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1 ) / 2;

        }
    }

    public static void heapify(int[] arr, int index, int heapSize) {
        int left = 2 * index + 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ?
                            left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }

    }

    public static void radixSort(int[] arr, int l, int r, int digit) {
        int[] bucket = new int[r - l + 1];
        final int radix = 10;
        int i, j;
        for (int d = 1; d <= digit ; d++) {
            int[] count = new int[radix];
            for (i = l;i <= r;i++) {
                j = getDigit(arr[i],d - 1);
                count[j]++;
            }

            for (i = 1; i < radix ; i++) {
                count[i] += count[i - 1];
            }
            for (i = r; i >= l; i--) {
                j = getDigit(arr[i],d - 1);
                bucket[count[j] - 1] = arr[i];
                count[j]--;
            }
            for (i = l,j = 0;i <= r; i++, j++) {
                arr[i] = bucket[j];
            }
        }
    }

    public static int getDigit(int num, int d) {
        return num / (int)Math.pow(10, d) % 10;

    }

    public static int maxDigit(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(arr[i], max);
        }
        int res = 0;
        while (max != 0) {
            res++;
            max /= 10;
        }
        return res;
    }
}

/*
 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        int n = 0;
        while (cur1.next != null) {
            ++n;
            cur1 = cur1.next;

        }
        while (cur2.next != null) {
            --n;
            cur2 = cur2.next;
        }
        cur1 = n < 0 ? headB : headA;
        cur2 = cur1 == headB ? headA : headB;
        n = Math.abs(n);
        while (n != 0) {
            cur1 = cur1.next;
            --n;
        }
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }
 */

/*
public void reorderList(ListNode head) {
        if(head.next == null || head.next.next == null) {
            return;
        }
        ListNode p1 = head;
        ListNode p2 = head;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        p2 = p1.next;
        p1.next = null;
        ListNode p3 = p2.next;
        while (p2.next != null) {
            p2.next = p1;
            p1 = p2;
            p2 = p3;
            p3 = p3.next;
        }
        p2.next = p1;
        p3 = head;
        ListNode next = p3.next;
        while (next !=null && p1 != null) {
            next = p3.next;
            p3.next = p2;
            p2.next = next;
            p2 = p1;
            p1 = p1.next;
            p3 = next;
        }
    }
 */

/*
  public Node copyRandomList(Node head) {
        if (head == null) {
            return head;
        }
        Node cur = head;
        Node next = null;
        Node copyNode = null;
        while (cur != null) {
            next = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = next;
            cur = next;
        }
        cur = head;
        while (cur != null) {
            next = cur.next.next;
            copyNode = cur.next;
            copyNode.random = cur.random == null ? null : cur.random.next;
            cur = next;
        }
        Node res = head.next;
        cur = head;
        while (cur != null) {
            next = cur.next.next;
            copyNode = cur.next;
            cur.next = next;
            copyNode.next = next == null ? null : next.next;
            cur = next;
        }
        return res;
    }
 */

/*
public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode p1 = head, p2 = head.next;
        ListNode prev = newHead;
        boolean flag = false;
        while (p2 != null) {
            while (p2 != null && p2.val == p1.val) {
                flag = true;
                p2 = p2.next;
            }
            if (p2 == null) {
                prev.next = null;
                break;
            }
            if (flag) {
                prev.next = p2;
                p1 = p2;
                p2 = p2.next;
                flag = false;
            } else {
                prev = p1;
                p1 = p1.next;
                p2 = p2.next;
            }

        }
        return newHead.next;
    }
 */

/*
public ListNode oddEvenList(ListNode head) {
        while (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        ListNode oddHead = new ListNode(0);
        ListNode evenHead = new ListNode(0);
        ListNode odd = oddHead;
        ListNode even = evenHead;
        int k = 1;
        while (head != null) {
            if (k % 2 != 0) {
                odd.next = head;
                odd = head;
            } else {
                even.next = head;
                even = head;
            }
            head = head.next;
            ++k;
        }
        odd.next = evenHead.next;
        even.next = null;
        return oddHead.next;
    }
 */